#include <iostream>
using namespace std;
void merge(int *a, int start, int middle, int end, int *temp)
{

	int i=start;
	int j=middle+1;
	int k=0;
	while(i<=middle&&j<=end)
	{
		if (a[i]<=a[j])
		{
			temp[k++]=a[i++];
		}
		else
		{
			temp[k++]=a[j++];
		}
       
	}
	while(i<=middle)
	{
		temp[k++]=a[i++];
	}
	while(j<=end)
	{
		temp[k++]=a[j++];
	}

	for(int m=0;m<k;m++)
	{
		a[start+m]=temp[m];
	}
}
void mergesort(int *a, int start, int end, int *temp)
{
	int mid=(start+end)/2;
	if (start<end)
	{
		mergesort(a,start,mid,temp);
		mergesort(a,mid+1,end,temp);
		merge(a,start,mid,end,temp);
	}
}

//int main()
//{
//
//
//	int arry[]={3,5,3,6,4,7,5,7,4};
//	int len=sizeof(arry)/sizeof(arry[0]);
//	int *newarray=new int[len];
//	memset(newarray,0,len);
//	mergesort(arry,0,len-1,newarray);
//	//merge(arry,0,4,8,newarray);
//	for (int i=0;i<len;i++)
//	{
//		cout<<newarray[i]<<" ";
//	}
//	cout<<endl;
//	return 0;
//}